/**
 * Animation of Tarjan's algorithm for detection of connected components
 * Authors: Andrei Haidu , Moritz Fuchs
 */

#include <iostream>
#include <climits>
#include <LEDA/graphics/graphwin.h>
#include <LEDA/graphics/color.h>

#include <LEDA/core/stack.h>
#include <LEDA/core/set.h>

#include "control.h" // Fernbedienung

using namespace leda;



void display_node_markers(GraphWin &gw , node &v , node_array<int> pre , node_array<int> lowlink , int component = 0) {
	string label = "pre: " + string("%i" , pre[v]) + " \nlowlink: " + string("%i" , lowlink[v]);
	if (component != 0)
		label += "\ncomponent: " + string("%i" , component);
	gw.set_user_label(v , label);
}

/**
 * Color a component
 */
void color_component(graph &g , GraphWin &gw, node_array<int> component, list<node> component_stack, int component_number, node_array<int> &pre , node_array<int> &lowlink) {

	gw.message("Coloring component number " + string("%i" , component_number));

	list<node>::iterator it;
	node v;
	edge e;

	//go through nodes of the component, mark them and their 'good' edges
	for (it = component_stack.begin(); it != component_stack.end(); it++) {
		//color node green
		v = *it;
		display_node_markers(gw , v , pre , lowlink , component[v]);
		//gw.set_user_label(v , string("%i" , component_number));
		gw.set_color(v , blue);
		forall_out_edges(e,v) {
			node target = g.opposite(e , v);
			//check if the target of this edge is in the component. If so, mark it as part of the component
			if (component[v] == component[target]) {
				gw.set_color(e , blue);
				gw.set_width(e , 2);
				gw.set_style(e , solid_edge);
			} else {
				//if edge is not part of the component color it red and make it thin
				gw.set_color(e , red);
				gw.set_width(e , 1);
				gw.set_style(e , solid_edge);
			}
		}
		control_wait(1);
	}

	gw.del_message();

}

/**
 * Tarjan's algorithm for detecting connected components
 */
void strongly_connected_recursion
(node v ,
 node parent,
 graph &g,
 GraphWin &gw,
 node_array<int> &pre,
 node_array<int> &component,
 node_array<int> &lowlink,
 int &akt ,
 int &component_counter,
 stack<node> &s ,
 node_array<bool> &stack_marker) {

	//labels get too big to be displayed inside a node, therefore we display them next to it.
	gw.set_label_pos(v , east_pos);

	// set dfs number
	pre[v] = akt++;
	//initialize low and lowlink with the dfs-number of the node
	lowlink[v] = pre[v];

	//push current node to stack
	s.push(v);
	//mark the node as currently in the stack
	stack_marker[v] = true;

	display_node_markers(gw , v , pre , lowlink);
	//mark node as active
	gw.set_color(v, red);
	control_wait(0.5);

	edge e;
	// Go through all neighbors of this node
	forall_out_edges(e, v) {
		//target node at the other end of e
		node target = g.opposite(v, e);
		//ignore self-loops
		if (target != v) {
			 // node was not yet visited, so we recurse
			if (pre[target] < 0) {
				//make edge red, bold since it is now 'active'
				gw.set_color(e , red);
				gw.set_width(e , 2);

				//recursive call
				strongly_connected_recursion(target, v, g, gw, pre,component,lowlink, akt, component_counter, s, stack_marker); // rekursiver Aufruf fuer w

				//Check values of low[target] / lowlink[target] and update low[v] / lowlink[v] accordingly
				lowlink[v] = std::min(lowlink[target] , lowlink[v]);

				//update labels of node v
				display_node_markers(gw , v , pre, lowlink);

				//shrink edge back to normal size and color it blue to indicate that it is done
				gw.set_width(e , 1);
				gw.set_color(e , green);
				control_wait(0.5);

			} else {
				//target node was already visited. We have to check what kind of edge this is

				//backward, forward or cross edge
				if (pre[target] < pre[v]) {
					if (stack_marker[target]) {
						//we found a backward edge. Update the lowlink value and mark the edge as backward edge (dotted)
						lowlink[v] = std::min(pre[target] , lowlink[v]);

						//update labels for v
						display_node_markers(gw , v , pre , lowlink);

						gw.set_style(e , dotted_edge);
						gw.set_color(e, grey3);
					} else {
						//We won't use this edge. Color it red
						gw.set_color(e , red);
					}
					control_wait(0.5);
				}
			}
		}
	}
	//this node is done, color it as 'visited'
	gw.set_color(v , green);
	control_wait(0.5);

	//Check if v is the root of a strongly connected component
	if (pre[v] == lowlink[v]) {
		//a new component was found, increase counter
		component_counter++;

		node w;
		list<node> component_stack;
		//collect all nodes of this component
		do {
			w = s.pop();
			component_stack.append(w);
			component[w] = component_counter;
			//we popped w; update the stack marker
			stack_marker[w] = false;
		} while (w != v);

		//color the component and its edges
		color_component(g, gw, component , component_stack ,  component_counter,lowlink,pre);
	}

	gw.redraw();
}

/**
 * Wrapper for Tarjan's algorithm
 * Initializes the variables and calls Tarjan's algorithm until all nodes have been visited
 * Parameter:
 * g: graph as reference
 * gw: visualization window as reference
 **/
void strongly_connected(graph &g, GraphWin &gw) {

	//initialize arrays for the dfs number , low and lowlink
	node_array<int> pre(g , -1);
	node_array<int> low(g , -1);
	node_array<int> lowlink(g , -1);

	//marker to indicate whether a node is currently in the stack or not
	node_array<bool> scc_marker(g , false);

	stack<node> s;

	//counters for the bfs number
	int akt = 0;
	//counter for the number of components
	int component_counter = 0;

	node v;
	//call the algorithm until all nodes have been visited
	forall_nodes(v , g) {
		if (pre[v] == -1) {
			strongly_connected_recursion(v , v , g , gw , pre , low , lowlink , akt , component_counter, s , scc_marker);
		}
	}

	gw.message(string("%i" , component_counter) + " components found.");
}


int main(int argc, char *argv[]) {
    //display window of size 800 x 600
    GraphWin gw(800, 600);
    gw.display();

    //show control
    create_control();
    //directed graph
    gw.set_directed(true);
    //load graph if specified
    if (argc > 1)
        gw.read(argv[1]);

    //go to edit mode
    gw.edit();

    //get the edited graph
    graph &g = gw.get_graph();

    //exit if the graph is empty
    if (g.number_of_nodes() == 0) {
        gw.close(); destroy_control();
        exit(1);
    }

    //initialize colors, color graph grey.
    node v;
    forall_nodes(v, g) {
        gw.set_label_type(v, user_label);    // User-Label anzeigen (statt Index-Label)
        gw.set_color(v, grey3);
    }
    edge e;
    forall_edges(e, g)
        gw.set_color(e, grey3);


    //mark all connected components in g
    strongly_connected(g, gw);

    //tell user that we are ready
    gw.acknowledge("Ready!");
    //let user edit the graph again
    gw.edit();

    //cleanup
    gw.close();
    destroy_control();
    exit(0);
}
